#include "stdio.h"
#include "assert.h"
#include "stdlib.h"



typedef int ElemType;
typedef struct DNode{
  ElemType data;
  struct DNode* pre;  
  struct DNode* next;  
}DNode; 
typedef DNode* DoubleList;

void initDoubleList(DoubleList* p);
void DoubleList_push(DoubleList* p,ElemType data);
ElemType DoubleList_pop(DoubleList* p);
void DoubleInsert(DoubleList* p,int position,ElemType data);
void printfNode(DoubleList* p);


void main(){
   DoubleList myList;
   initDoubleList(&myList); 

   DoubleInsert(&myList,1,100);
   printfNode(&myList);
 
}

void initDoubleList(DoubleList* p){
     assert((*p) != NULL);
    (*p) = NULL;
    printf("��ʼ��\n");
}


void DoubleList_push(DoubleList* p,ElemType data){
	 DoubleList newNode = malloc(sizeof(DNode)); 
	 (*newNode).data =  data;
	 (*newNode).pre = NULL;
	 (*newNode).next = NULL;
	
     if((*p) == NULL){
	   (*p) = newNode;
	   return;
	 }
	 DoubleList curNode = (*p);
	 while((*curNode).next != NULL){
	    curNode = (*curNode).next;
	 }
	 (*newNode).pre = curNode;
	 (*curNode).next = newNode;	 	 
}

ElemType DoubleList_pop(DoubleList* p){
	
     if((*p) == NULL){
	   printf("��˫������Ϊ�գ��޷�ɾ��Ԫ��");
	   return -9999; 	   
	 }

     DoubleList curNode = (*p);
     ElemType popData;
	 while((*curNode).next != NULL){
	    curNode = (*curNode).next;
	 }
	  // ֻ��һ���ڵ� 
	 if((*curNode).pre == NULL){
	 	popData = (*curNode).data;
	    free(curNode);
	    (*p) = NULL;
	    return popData;
	 }
	 
	 DoubleList preNode = (*curNode).pre;
	 popData = (*curNode).data;
	 (*preNode).next = NULL;
	 free(curNode); 
	 return popData;  	 
}

void DoubleInsert(DoubleList* p,int position,ElemType data){
	
      DoubleList curNode =  (*p);
      DoubleList preNode;
      DoubleList nextNode;
      
      int curPosition = 1;
      // Ѱ��λ�� 
      if(position <= 0){
	   printf("���������Ԫ�ص�λ������\n");
	   return;
	   }
	    printf("����\n"); 

      while((*curNode).next != NULL){
	     curNode = (*curNode).next; 
	     curPosition+=1; 
	     if(curPosition == position)break;
	  }
	  printf("����\n"); 
	  if(position>curPosition+1){
	     printf("���������Ԫ�ص�λ������\n");
	     return;
	  }
	  preNode  =  (*curNode).pre;
	  nextNode = (*curNode).next;
	     
	  // �����½ڵ� 
	    DoubleList newNode = malloc(sizeof(DNode)); 
    	(*newNode).data =  data;
	    (*newNode).pre = NULL;
	    (*newNode).next = NULL;
	     
	  
	 if(position == 1 && curNode == NULL ){
	    (*p) = newNode;
	 
	     return;
	  } 
	  if(position == 1){
	  	 DoubleList temNode = (*p);
	  	 (*temNode).pre = newNode;
	  	 (*newNode).next = temNode;	 
	  	  return;
	  } 
	  if(position == curPosition+1){
	      (*newNode).pre = curNode;
	      (*curNode).next =  newNode;
	       return;
	  }
	  (*newNode).pre = preNode;
	  (*newNode).next = curNode;
	  (*preNode).next = newNode;
	  (*curNode).pre = newNode;	  	  	  
}






void printfNode(DoubleList* p){
    if((*p) == NULL){
	   printf("��˫������Ϊ�գ��޷���ӡ");
	   return;
	 } 
	 int i = 1;
	 DoubleList curNode = (*p);

	 while(curNode != NULL){
	   printf("��%d��Ԫ�ص�ֵΪ%d\n",i,(*curNode).data) ;
	   curNode = (*curNode).next;
	   i++; 
	 }
	 
}






